package 数组;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/search-insert-position/
 */
public class _35_搜索插入位置 {

    /**
     * 二分法  通过mid取值对比 如果大于target  则对比mid右侧  反之  对比mid左侧
     * @param nums 目标数组
     * @param target 目标值
     * @return int
     */
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int mid = n >> 1;
        int left = 0;
        int right = n;

        // 特殊情况排除
        if (nums[n - 1] < target) {
            return n;
        } else if (nums[left] >= target) {
            return left;
        }
        /*
            判断存在左侧还是右侧
         */
        while (left < right) {
            if (nums[mid] > target) {
                right = mid - 1;
                mid = (left + mid) >> 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
                mid = (mid + right) >> 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        // 如果得出的结论 大于 target 则返回mid  否则 返回mid + 1
        return nums[mid] > target ? mid : mid + 1;
    }

    /**
     * 官方二分法答案
     *
     * @param nums 目标数组
     * @param target 目标值
     * @return int
     */
    public int searchInsert2(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
